import com.sun.source.tree.ParenthesizedPatternTree;

public class Sort5 {
//    这里是从小到大进行排序,所以要构建大根堆.
    public static void createHeap(int[] array){
//      这里的做法是从最后一颗树开始,向下调整
        for(int parent=(array.length-1-1)/2;parent>=0;parent--){
//            对每一棵子树都进行调整,最后得到的树就是有序的.
            siftDown(array,parent,array.length);
        }
    }
    public static void siftDown(int[] array,int partent,int end){
        int child=2*partent+1;
//        这里是对树的范围进行了约束
        while(child<end){
          if(child+1<end&&array[child+1]>array[child]){
              child++;
          }
//          判断是否要进行交换
          if(array[child]>array[partent]){
              swap(array,partent,child);
//              交换之后,就要向下调整,无法确定下面的树是否有效
              partent=child;
              child=2*partent+1;
          }else{
              break;
          }
        }
    }
    public static void swap(int[] array,int i,int j){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;

    }
//    堆排序,如果是升序排序,就要创建大根堆.反之.
    public void heapSort(int[] array){
//        升序排列,先创建大根堆
        createHeap(array);
//        从最后一个元素,开始对调,对调后向下调整.对调到第一个元素.即完成了排序
        int end=array.length-1;
        while(end>0){
            swap(array,0,end);
            siftDown(array,0,end);
            end--;

        }
    }








}
//这里是堆排序
